#include <iostream>
#include<string>
#include<vector>
using namespace std;

class Solution {
public:
vector<string> nTos={"", "", "abc", "def", "ghi","jkl","mno","pqrs","tuv","wxyz"};
    void Combinations(const string& digits,size_t di,string str,vector<string>& res)
    {
        if(di==digits.size())//结束条件，组合的字符长度==数字长度
        {
            res.push_back(str);
            return;
        }
        int num=digits[di]-'0';
        string number=nTos[num];//获取相应数字的字母映射
        for(auto ch:number)
        {
            Combinations(digits,di+1,str+ch,res);//str是每次组合的字母+要组合的字母
        }
    }
    vector<string> letterCombinations(string digits) {
        vector<string> res;//存入每次组成的字母组合
        if(digits.empty()) return res;

        string str;//可以组成的字母组合
        Combinations(digits,0,str,res);
        return res;
    }
};